//
// Created by lanlu on 2025/8/6.
//

#include <iostream>
#include <stack>
#include <string>
using namespace std;

// 返回单个运算符的优先级
int getPriority(char op)
{
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

// 弹栈并计算 传入栈本身 使用引用类型
void popAndCalc(stack<int> &num_stack, stack<char> &op_stack)
{
    char op = op_stack.top();
    op_stack.pop();

    int num1 = num_stack.top();
    num_stack.pop();
    int num2 = num_stack.top();
    num_stack.pop();

    int result = 0;
    switch (op)
    {
        case '+':
            result = num1 + num2;
            break;
        case '-':
            result = num2 - num1;
            break;
        case '*':
            result = num1 * num2;
            break;
        case '/':
            result = num2 / num1;
            break;
    }
    num_stack.push(result);
}

// 中缀表达式求值
int calc(string s)
{
    // 声明数值栈 和 运算符栈
    stack<int> num_stack;
    stack<char> op_stack;

    // 记录上一个有效字符 是不是运算符
    bool flag = false;
    for (int i = 0; i < s.size(); i++)
    {
        char c = s[i];
        // 如果是空格则跳过
        if (isspace(c)) continue;

        // 直接判断字符是否是数字
        if (isdigit(c))
        {
            // 如何处理多位数字
            // 如果当前字符是数字 往后进行遍历 直到不是数字
            //   遍历第二个数字时 和第一个进行拼接 num = 10 * num + c - '0'
            int num = 0;
            while (i < s.size() && isdigit(s[i]))
            {
                num = num * 10 + (s[i] - '0');
                i++;
            }
            num_stack.push(num);
            // 如果下一位不是数字 需要回退
            i--;
            flag = false;
        }
        else if (c == '(')
        {
            op_stack.push(c);
            flag = true;
        }
        else if (c == ')')
        {
            while (op_stack.top() != '(')
            {
                // 弹栈并计算
                popAndCalc(num_stack, op_stack);
            }
            op_stack.pop();
            flag = false;
        }
        else if (c == '-')
        {
            // 如何区分负号 还是 减号
            // 负号的几种情况： 第一位就是负号 左括号紧跟着负号 或者运算符后面跟着负号
            // 这里还有一种情况是  1+(  -2)
            if (i == 0 || s[i - 1] == '(' || flag)
            {
                // 将负号 看做 -num = 0 - num
                num_stack.push(0);
            }

            while (!op_stack.empty() && op_stack.top() != '('
                   && getPriority(op_stack.top()) >= getPriority(c))
            {
                popAndCalc(num_stack, op_stack);
            }
            op_stack.push(c);
            flag = true;
        }
        else
        {
            // +-*/
            // 如果栈不为空 且 栈顶运算符不是左括号
            // 且 栈顶运算符优先级 >= 当前运算符 则弹栈并计算
            while (!op_stack.empty() && op_stack.top() != '('
                   && getPriority(op_stack.top()) >= getPriority(c))
            {
                popAndCalc(num_stack, op_stack);
            }
            op_stack.push(c);
            flag = true;
        }
    }

    while (!op_stack.empty())
    {
        popAndCalc(num_stack, op_stack);
    }
    return num_stack.top();
}

int main()
{
    // cout << calc("(11+2)*3-4/5") << endl;
    // cout << calc("1+(  -3)") << endl;
    // cout << calc("-3*-3") << endl;
    return 0;
}
